Almathera Ten Pack 3: CDPD 3

home *** CD-ROM | disk | FTP | other *** search

/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / scope / 151-175 / scopedisk152 / atree / numbering_tutorial < prev next >

Wrap

Text File | 1995-03-19 | 18.7 KB | 515 lines

The Binary and Hexadecimal Numbering Systems The binary and hexadecimal numbering systems are very important in computer science and anyone wishing to advance their knowledge of the subject to attain a deeper understanding of computers must learn them. In order to understand and use the Atree Sector Editor, an understanding of at least the hexadecimal numbering system is necessary. This tutorial is presented to assist users in fully exploiting the power of Atree and its secotr editor. The binary and hexadecimal numbering systems are just two of an infinite number of possible numbering systems. And all numbering systems have the same properties. Once these properties are understood for numbering systems in general it becomes very easy to understand any numbering system and even design your own. This tutorial therefore is designed to bring you to an understanding of numbering systems in general first. Then our discussion of the binary and hexadecimal systems will be a snap. We will start with what is undoubtedly familiar to everyone -- the base 10 numbering system. This is the counting or numbering system we all learned in grammar school and use almost daily without thinking about it much. In the base 10 system there are ten digits -- 1 thru 9, and 0. This is a very significant fact. In the base 5 system there are 5 digits -- 1 thru 4, and 0. In the base 8 system there are 8 digits, 1 thru 7, and 0. The general rule is that in the base x system, there are x digits. There are 1 to x-1 digits which are related to each other by the property that each succeeding digit is equal to the former digit plus one. And there is always a digit representing the concept of nothing -- 0. With only ten digits, how do we count or number greater than 9? Well, you all probably remember from your grammar school years that we organize digits in columns -- remember the one's column, the ten's column, the hundred's column? A number like 728 means 8 one's, two ten's, and 7 hundred's. To obtain the value of 728, we actually multiply 8 times 1, and add it to 2 times 10, and then add this result to 7 times one hundred. Notice that one, ten and one-hundred are all powers of ten, the base of our numbering system. In fact, that's why 10 is called the base. One is 10 to the power 0; 10 is 10 to the power 1, and one-hundred is 10 to the power 2. Each column of a number represents another power of 10. Thus, we can have a thousand's column (10 to the third power, or ten cubed), and a ten-thousand's column (10 to the fourth power), etc. Now think about how we count. When we get up to 9 in the one's column, we then write "10" as the next number. When we get up to 19, we then write "20" as the next number. When we get to 99 we then write "100" as the next number. Think of the mileage indicator on your car. It starts at the factory with all columns set to 0's. Each column is represented by a small cylinder with the numbers 1,2,3,4,5,6,7,8,9,0 written evenly around the outer edge. Each cylinder does nothing but go around in circles repeatedly as you drive. But the cylinder's are interrelated so that every time a given cylinder completes one cycle and returns to "0", the cylinder immediately to the left then rolls to its next digit. Now let's rethink what we have said so far using a base 5 system. We will have only five digits; 1 thru 4 and 0. We will still have our one's, ten's, hundred's column, etc., but the values of these columns will not be powers of ten -- they will be powers of five, the base. The one's column will have a value of 5 to the 0 power (or 1), the ten's column will have a value of 5 to the power of 1 (or 5), the hundred's column will have a value of 5 to the power of 2 (or 25), and so on. Note that in the base 5 system, you cannot have a number like 732 -- the seven is not defined. You can have numbers like 423, 122, 444, 1000. But they won't mean the same thing as in the base 10 system. In the base ten system, 444 means 4 hundreds, plus 4 tens, plus 4 ones. But in the base five system, 444 means 4 twenty-fives (which would be the equivalent of 100 in the base ten system), 4 fives (which would be the equivalent of 20 in the base ten system), and 4 ones (which has the same value in both systems). So, 444 in the base five system is equivalent to 124 in the base ten system. Study closely the parallel method of calculating the value of 444 in the base 10 system on the one hand and in the base 5 system on the other: Base 10 value of 444 = 4 X 10 X 10 = 400 4 X 10 = 40 4 X 1 = 4 TOTAL = 444 Base 5 value of 444 = 4 X 5 X 5 = 100 4 X 5 = 20 4 X 1 = 4 TOTAL = 124 What would 292 (base 10) be in the base 5 system? Well, obviously what we would like to have as our end result is a base five number such that when we do the kind of conversion we did on 444 above we end up with 292 as its base ten equivalent. This number we are shooting for will have digits in it representing powers of five. Let's look at the powers of five up to the fourth power: 5 to the 0 = 1 5 to the 1 = 5 5 to the 2 = 25 5 to the 3 = 125 5 to the 4 = 625 What we want to do is represent 292 as a sum of numbers which are multiples of powers of five. It is easy to intuitively notice in this case that 292 can be represented as: (a) 2 X 125 + 1 X 25 + 3 X 5 + 2 X 1 This is equivalent to: (b) 250 + 25 + 15 + 2 And this adds up to 292. Moreover, (a) above is the key to our conversion; 125 represents the base five "thousands" column; 25 is the base five "hundreds" column, and 5 is the base five "tens" column. So the base five number we are looking for is 2132. To double check our work, we can convert the base five number 2132 into its base ten equivalent. The 2 represents 2 times five to the third power (which is 250), and the 1 represents 1 times five to the power of 2 (which is 25), and the 3 is 3 times the power of five to the power of 1 (which is 15), and finally add in the 2; all this gives 292. Let's try converting the base ten number 2398 into its base five equivalent. Remember, what we want to do is represent this number as the sum of a series of multiples of powers of five. There is a very systematic and easy to follow technique for doing this. The first question you ask is, "What is the largest power of five that will divide the number with a result greater than one?" In our little table of powers of five above, we note that five to the power of two (25) divides the number with a result larger than one, but it is not the largest power of five that does so. Five to the power of three (125) also divides 2398 with a result larger than one, but so does five to the power of 4 (625). Five to the power of 5 (3125) does not divide 2398 with a result larger than one, so therefore five to the power of 4 (625) is the answer to our first question -- it is the largest power of five that divides our number, 2398, with a result that is larger than one. The next step is to actually do the division and determine the remainder. In this case, 2398 divided by 625 yields 3 with a remainder of 523. We may now write 2398 as: (a) 3 X 625 + 523 = 2398 Now, we deal with the remainder of 523 and divide it by the next smaller power of five. 625 is five to the fourth power, so the next smaller is therefore five cubed, which is 125. 523 divided by 125 yields 4 with a remainder of 23. 523 can therefore be represented as: (b) 4 X 125 + 23 = 523. Substituting (b) for the 523 in (a), we get: (c) 3 X 625 + 4 X 125 + 23 = 2398 Now we look at the remainder of 23. And we divide it by the next smaller power of five. The next smaller power of five is now 25. 23 divided by 25 yields a result of 0 with a remainder of 23. So we now re-write line (c) above as: (d) 3 X 625 + 4 X 125 + 0 X 25 + 23 = 2398 We again look at the remainder of 23 and again we divide by the next smaller power of five, which this time is 5. 23 divided by 5 yields 4 with a remainder of three. So we can re-write (d) above as: (e) 3 X 625 + 4 X 125 + 0 X 25 + 4 X 5 + 3 = 2398 Our remainder of 3 is now exactly divisible by the next smaller (and last) power of five (which is five to the 0 = 1). It is now obvious that the base five equivalent of the base ten number, 2398, is 34043. What we did to get 34043 was to simply take the digits that we needed to multiply with the decreasing powers of 5 (625, 125, 25, 5, 1) to get our base 10 number. The Binary Number System What is called the binary number system simply has a base of 2. That means there are only two digits -- 0 and 1. Let's take a four digit binary number and start counting -- remember the cylinder process: Base 10 Binary 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 10 1010 11 1011 12 1100 13 1101 14 1110 15 1111 Since we are dealing with the base 2 system, the columns from right to left represent increasing powers of 2, starting with 2 to the power of 0 = 1, then 2 to the power of 1 = 2, then 2 to the power of 2 = 4, then 2 to the power of 3 = 8. The powers of 2 up to the 10th power are 1 ,2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. The binary representation of these powers of 2 would of course be: -------------------------------------------------- Power of two Binary number Decimal value -------------------------------------------------- 0 1 = 1 1 10 = 2 2 100 = 4 3 1000 = 8 4 10000 = 16 5 100000 = 32 6 1000000 = 64 7 10000000 = 128 8 100000000 = 256 9 1000000000 = 512 10 10000000000 = 1024 Let's do some converting. What would the binary number 1011001101 be in decimal? Let's first number the columns starting at the far right with the first column. We will start numbering with "0" so that our column numbers represent the powers of 2 we must use for the value in that column: 9 8 7 6 5 4 3 2 1 0 1 0 1 1 0 0 1 1 0 1 Now we can start calculating the decimal value of the binary number. We simply calculate the decimal equivalent of the value of each of the columns of the binary number. Since the columns that have a "0" in them will always evaluate to "0", we can ignore them. The columns number of the columns which have 1's in them are: 9 7 6 3 2 0 These represent the powers to which we have to raise the number 2 to determine the decimal value. The decimal values corresponding to these values of two are given in the small table above. We can rewrite the column numbers now with the decimal values of each colum: 9 512 7 128 6 64 3 8 2 4 0 1 Now we add up the decimal values in the right hand column above to get 717. What is the binary number whose decimal value is 946? Using the table above, we see that 512 is the highest power of 2 that divides 946 with a result greater than one. This value corresponds to 2 to the power of 9. Therefore, we are dealing with a nine digit binary number -- our result must have a value (either 0 or 1) in each of the columns, 0 thru 9. Let's write the number of these colums: 9 8 7 6 5 4 3 2 1 0 Now 512 divides 946 once with a remainder of 434. So we put a "1" below the 9. Column 8 represents 2 to the power of 8 which is 256. 256 divides 434 once with a remainder of 178. So se can put a "1" below it too. Column 7 represents 2 to the power of 7 which is 128. 128 divides 178 once with a remainder of 50. So we can put a "1" below it. Column 6 represents 64 and 64 does not divide 50 with a result greater than one. So se put a "0" in column 6. Column 5 represents 32 and 32 divides 50 once with a remainder of 18. Se we can put a 1 in column 5. Column 4 represents 16. 16 divides 18 once with a remainder of 2. So we put a "1" in column 4. Columns 3 and 2 represent 8 and 4 respectively and niether of these divides 2 more than once, so we put 0's in both column 3 and column 2. Column 1 represnets 2 and 2 divides 2 once with a remainder of 0. So we put a 1 in column 1. Since the remainder is 0, we put a 0 in column 0. We end up with 1110110010 (base 2) = 946 (base 10). Why are binary numbers so important to the study of computer science? The reason is that a computer's memory is made up of hundreds of thousands, or even millions, of tiny transistors. A transistor is an electronic component that has two states -- it either acts to greatly restrict the flow of current through it, or it acts to let the current flow quite freely. Hence it is spoken of as being either "on" (allowing high current flow, hence high voltage), or "off" (allowing low current flow, hence low voltage). Obviously, the on/off or high/low states of transistors lend themselves to binary interpretation -- 1 or 0. You can string a number of transistors together and let each one represent a column of a binary number. In fact, that's just what computer engineers do. And the typical number of transistors so strucg together is 8. Hence, a very standard computer number is an 8 digit (or 8 column, if you wish) binary number. An 8 digit binary number is called a byte. The digits or columns are of course numbered 0 thru 7 (instead of 1 thru 8) so that the column number represents the power of 2 that the column represents. Each column is called a bit. Thus, we speak of bit 7, or bit 6, or the zero bit. The low bit of a binary number is always bit zero. The high bit is always the highest bit of the number. Thus, the high bit of a byte is bit 7. The low bit is also referred to as the Least Siginificant Bit, or LSB. The high bit is also referred to as the MSB; Most Siginificant Bit. If the value of a bit is 1, the bit is said to be set. If it is 0, it is said to be clear. In the binary number 10110, the low bit is clear, the high bit is set. The high bit is bit 4; bit 3 is clear, and bits one and two are set. A byte can have values ranging from 00000000 to 11111111. The decimal equivalent is 000 to 255. There are a total of 256 values (0 - 255). In general, an x bit binary number has 2 to the power of x values, ranging from 0 to (2 to the powers of x) - 1. Thus, a byte, being an 8 bit binary number, has 2 to the power of 8 (256) values, ranging from 0 to 255. A 16 bit binary number has 2 to the power of 16 (or 256 X 256 = 65,536) values, ranging from 0 to 65,535. The first four bits of a byte are referred to as the low nibble; the last four bits are referred to as the high nibble. When we write decimal numbers, we conventionally use a comma every three columns to make the number easier to comprehend. Spaces are typically used for this purpose with binary numbers. Sometimes spaces are used between the nibbles of bytes. Thus 10110011 is written as 1011 0011. Alternatively, a space separates bytes in longer binary numbers. A 32 bit binary number is thus frequently rendered as four bytes separated by spaces. Thus, 10110011 01011100 10101111 00010010 The Hexadecimal Numbering System Don't be alarmed by the name -- we are simply talking about a base 16 numbering system. In the numbering systems we have looked at so far the base has always been less than 10. We therefore needed less than 10 symbols to represent our digits and we could therefore use the same ones we are familiar with from the base 10 system (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and 0). What do we do when we are dealing with number systems whose bases are larger than 10? We use all of the numbers from the base 10 system, and when we run out, we use the letters of the alphabet. Thus, the base 12 system would have 12 digits as follows: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B. The base 14 system would have 14 digits as follows: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D. And the base 16 (or hexadecimal) system would have 16 digits as follows: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. In all of the above, the symbols A thru F have the decimal equivalent values of 10 thru 15 respectively. Let's convert the hexadecimal number A7C034F into its decimal equivalent. First, let's determine the values of the columns. Our particular number has 7 columns, 0 thru 6. And we are dealing with powers of 16, the base. Let's write down the decimal values of these powers as follows: Power of 16 Decimal Value 0 1 1 16 2 256 3 4096 4 65536 5 1048576 6 16777216 Now we can re-write this table showing the digits of the hexadecimal number in the correct places: Power of 16 Decimal Value hex digit 0 1 F 1 16 4 2 256 3 3 4096 0 4 65536 C 5 1048576 7 6 16777216 A We can write this table one more time. This time, we will include the decimal values of the hex digits A thru F: Power of 16 Decimal Value hex digit Dec value of hex 0 1 F 15 1 16 4 4 2 256 3 3 3 4096 0 0 4 65536 C 12 5 1048576 7 7 6 16777216 A 10 Now, to get the decimal value of our hex number all we have to do is multiply the values in the "Decimal Value" column by the corresponding values in the "Dec value of hex" column and add the results together. The hexadecimal numbering system is very commonly used in computer science. Why? Because it has a very close relationship to the base 2, or binary numbering system. This relationship becomes clear when we examine a table showing the binary equivalent of the 16 hexadecimal digits. Hex Digit Binary Equivalent 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 A 1010 B 1011 C 1100 D 1101 E 1110 F 1111 Notice that four bits of a binary digit correspond to one hexadecimal digit. Therefore 8 bits correspond to two hex digits. A byte, in other words, can be represented as two hexadecimal digits. And to translate quickly from one to the other, all you need is the above table. Thus, 11100011 in binary is E3 in hex. A5 is 10100101 in binary. Learning to live comfortably with several numbering systems is a must for those interested in geting below the surface level of computer understanding. Playing with various numbering systems and playing with converting values from one to another is a good way of developing your comfort with them.